package com.example.websocket.sort;

import java.util.Arrays;

/**
 * 选择排序，从一个数开始寻找最小值并进行交换，依次向后寻找
 * -----------------------------------------------------------------------------------------
 * 简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；
 * 对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次。综合下来，
 * 时间复杂度为O(n^2)
 */
public class SelectionSort {

    public void selection(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min = nums[i];
            int temp = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    temp = j;
                }
            }
            nums[temp] = nums[i];
            nums[i] = min;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
        SelectionSort s = new SelectionSort();
        s.selection(array);
        System.out.println(Arrays.toString(array));
    }
}
